As a conventional compression technique of a multi-valued image, a method of segmenting an original image into blocks each consisting of a plurality of pixels, applying the two-dimensional (2D) DCTs, quantizing each coefficient by a designated quantization threshold value, and Huffman-encoding the quantization results is available.
As hardware implementation of 2D DCT transformation in such encoding process, the following proposal has been made. That is, the one-dimensional DCTs of image inputs, which are segmented into n×n rectangular blocks are computed to obtain n×n coefficients, the coefficients are written in a storage means having a capacity capable of storing the n×n coefficients, the written coefficients are read out after transposition conversion, and the one-dimensional DCTs of the readout coefficients are computed again, thereby consequently implement a 2D DCT transformation process.
FIG. 5 is a block diagram showing an example of the arrangement of such conventional 2D DCT transformation device.
Reference numeral 5001 denotes signal lines, which include n signal lines used to transfer n inputs input from an image supply system (not shown), and are connected to a selector 500. The selector 500 selects n inputs sent via the signal lines 5001 or n inputs sent via n signal lines 5004 in accordance with a control signal input via a select signal line 5005, and outputs the selected n inputs onto n signal lines 5002. The n signal lines 5002 are connected from the selector 500 to a one-dimensional DCT transformer 501. The one-dimensional DCT transformer 501 applies the one-dimensional DCTs to the n inputs, which are input via the signal lines 5002. The one-dimensional DCT transformer 501 outputs n one-dimensional DCT coefficients onto signal lines 5003 including n signal lines.
The signal lines 5003 are branched into two systems, one of which is connected to an encoder (quantizer; not shown), and the other of which is connected to a transposition converter 502. The transposition converter 502 has a block memory having a capacity capable of storing n×n coefficients input via the signal lines 5003, writes the n×n DCT coefficients input via the signal lines 5003 in that block memory, transposes and reads out them, and outputs every n coefficients onto signal lines 5004 in accordance with a clock signal (5007) and control signal (5008).
The operation of the overall conventional 2D DCT transformation device will be explained below using FIG. 5, and the timing charts shown in FIGS. 6A and 6B.
In this example, n=8. For the sake of simplicity, FIG. 3A shows the positions of 64 blocks obtained by segmenting data into 8×8 rectangular blocks, and numbers corresponding to the positions.
FIG. 4A shows the horizontal raster scan order, and FIG. 4B shows the vertical raster scan order, which orders are used in the following description.
First eight data are input via the signal lines 5001 at the head of a period 601 in the timing chart shown in FIG. 6A. These first eight data are represented by “h0” in FIG. 6A, and correspondence between this “h0” and the position numbers in the 8×8 rectangular blocks shown in FIG. 3A is as shown in FIG. 3B. As shown in FIG. 3B, each of “h0” to “h7” consists of eight data selected in the horizontal raster scan order. In the period 601, the control signal (5005) input to the selector 500 indicates “1”. In this example, when the control signal (5005) input to the selector 500 is “0”, the selector selects the signal lines 5004; when it is “1”, the selector 500 selects the signal lines 5001. Hence, data on the signal lines 5001, i.e., “h0”, are output onto the signal line 5002 in the period 601.
Likewise, data “h1” to “h7” are input to the selector 500 via the signal lines 5001 at the heads of respective periods 602 to 607, and are output onto the signal lines 5002 since the control signal (5005) is “1”. The control signal (5005) input to the selector 500 indicates “1” during the periods 601 to 608. Hence, the selector 500 selects the values on the signal lines 5001 and outputs them onto the signal lines 5002.
The data “h0” output from the selector 500 in the period 601 are input to the one-dimensional DCT transformer 501 via the signal lines 5002. In this example, assume that the one-dimensional DCT transformer 501 outputs transformed coefficients in synchronism with the leading edge of the clock signal (5007) when the value of a control signal (5006) is “1”.
As shown in FIG. 6A, the value of the control signal (5006) changes to “1” at the end of each of the periods 601 to 608 and periods 609 to 619. Therefore, the data “h0” input to the one-dimensional DCT transformer 501 undergoes one-dimensional DCT transformation in the period 601, and transformed coefficients are output onto the signal lines 5003 at the head of the period 602 in accordance with the control signal (5006) and clock signal (5007).
Likewise, the data “h1” to “h7” input to the one-dimensional DCT transformer 501 at the heads of the respective periods 602 to 608 undergo one-dimensional DCT transformation, and corresponding coefficients are output onto the signal lines 5003 at the heads of the respective periods 603 to 609.
The data “h0” to “h7” output from the one-dimensional DCT transformer 501 onto the signal lines 5003 at the heads of the respective periods 602 to 609 are input to the transposition converter 502 so as to undergo transposition, and are sequentially written in the internal block memory having the capacity capable of storing 64 data. Assume that this internal undergoes write or read access in synchronism with the clock signal (5007). The transposition converter 502 outputs data in synchronism with the leading edge of the clock signal (5007) when the value of the control signal (5008) is “1”.
In this manner, after all the data “h0” to “h7” are written in the internal block memory of the transposition converter 502, they are read out in the vertical raster scan order, and every eight data are output in accordance with the control signal (5008) and clock signal (5007). The eight data output in this way are represented by each of “v0” to v7” in FIG. 6A. Correspondence between these “v0” to v7” and the position numbers in the 8×8 rectangular blocks shown in FIG. 3A is as shown in FIG. 3C. As shown in FIG. 3C, each of “v0” to v7” consists of eight data selected in the vertical raster scan order.
The control signal (5008) changes to “1” at the end of the periods 609 to 616, as shown in FIG. 6A. Therefore, the data “v0” to v7” are sequentially output onto the signal lines 5004 at the head of the periods 610 to 617, and are sent to the selector 500.
Note that correspondence between eight data, which are contained in “h7” input from the one-dimensional DCT transformer 501 to the transposition converter 502 via the signal lines 5003 at the head of the period 609, and the position numbers in the 8×8 rectangular blocks shown in FIG. 3A is “56, 57, 58, 59, 60, 61, 62, 63”, as shown in FIG. 3C.
On the other hand, correspondence between eight data, which are contained in “v0” input from the transposition converter 502 to the selector 500 via the signal lines 5004 at the head of the period 610, and the position numbers in the 8×8 rectangular blocks shown in FIG. 3A is “0, 8, 16, 24, 32, 40, 48, 56”, as shown in FIG. 3C. That is, position number “56” in the 8×8 rectangular blocks shown in FIG. 3A appear in both data which form “h7” and “v0”. In order to input data with position number “56” as an element of “h7”, which is output from the one-dimensional DCT transformer 501 at the head of the period 609, to a RAM, and read it out in an identical clock cycle, that RAM must have some functions as a condition. The condition includes that a readout value corresponding to a given address is output within an identical clock cycle in response to an address input, i.e., the RAM is an asynchronous RAM, and the RAM can write data at a given address and can read out the written data within an identical clock cycle. However, the clock frequencies in recent LSIs are increasing, and use of an asynchronous RAM in such system is disadvantageous. Hence, it is a common practice to use a synchronous RAM. A RAM that can read out the written value within an identical clock cycle is special, and not all RAMs have this function. Especially, in order to configure a circuit that can be implemented on various processes, such special RAM should not be used. Therefore, a general synchronous RAM must be assumed as a RAM to be used. This means that input of “h7” to the transposition converter 502 and output of “v0” from the transposition converter 502 cannot be done within an identical clock cycle unless a RAM that satisfies the aforementioned condition is used.
For this reason, output of “v0” from the transposition converter 502 must be delayed one clock cycle from input of “h7” to the transposition converter 502. FIG. 6B shows detailed operations during the periods 608 to 610.
FIG. 6B shows the clock signal (5007), which is not shown in FIG. 6A.
In FIG. 6B, the data “v0” to “v7” that have undergone transposition conversion are input to the selector 500 via the signal lines 5004. The control signal (5005) is switched to “0” to select the signal lines 5004 at the head of the period 610 so as to execute the second one-dimensional DCT transformation. Therefore, the data “v0” to “v7” are sequentially output from the selector 500 onto the signal lines 5002 and are input to the one-dimensional DCT transformer 501 at the heads of the respective periods 610 to 617.
The data “v0” to “v7” input to the one-dimensional DCT transformer 501 undergo second one-dimensional DCT transformation by the one-dimensional DCT transformer 501, and are sequentially output onto the signal lines 5003 at the heads of the respective periods 611 to 618 in accordance with the control signal (5006). The data which are sequentially output at the heads of the respective periods 611 to 618 have undergone the two one-dimensional DCT transformation processes via transposition conversion, and are consequently equivalent to the 2D DCT transformation result.
Subsequently, the control signal (5005) is switched to “1” at the head of the period 618 so as to select the signal lines 5001 and to receive the next 8×8 rectangular block data. First eight data “h0” of the next 8×8 rectangular blocks are input from the image supply system (not shown) to the selector 500 via the signal lines 5001 at the head of the period 618. After that, DCT transformation is similarly done every 8×8 rectangular blocks.
Conventionally, some proposals have been made to achieve high-speed processes while suppressing an increase in circuit scale in an encoding apparatus, that executes an orthogonal transformation process of image data, which is segmented into blocks each consisting of a plurality of pixels, for respective segmented blocks, rearranges the transform coefficients obtained by the orthogonal transformation process in a predetermined scan order, executes a quantization process of the rearranged transform coefficients using a predetermined quantization threshold value, and encodes the quantization result. Especially, in order to improve the use efficiency of a divider with a large circuit scale in the circuit arrangement of a quantization processor, a method of comparing a plurality of pairs of orthogonally transformed coefficients and corresponding quantization threshold values at the same time to see whether the quantization result becomes zero (insignificant coefficient) or not (significant coefficient), and preferentially inputting coefficients that do not yield zero results to the divider is known.
FIG. 16 shows the arrangement of a conventional encoding apparatus.
An orthogonal transformer 9801 executes an orthogonal transformation process of image data, which is segmented into blocks each consisting of a plurality of pixels, for respective segmented blocks, and sequentially outputs obtained coefficients to a block memory 9802. This orthogonal transformer 9801 corresponds to, e.g., the 2D DCT transformation device shown in FIG. 5. The orthogonal transform coefficients output from the orthogonal transformer 9801 are written in the block memory 9802, and every two coefficients are read out in a zigzag scan order in accordance with a control signal output from a controller 9810 when the orthogonal transform coefficients for one block are written. FIG. 13 shows the zigzag scan order when each block as a unit of orthogonal transformation is formed of 8×8 elements.
Two coefficients read out from the block memory 9802 are respectively input to comparators 9803 and 9804. At the same time, the two coefficients read out from the block memory 9802 are also input to a selector 9807. On the other hand, two quantization threshold values corresponding to the two readout coefficients are read out from a quantization threshold value table 9805, and are input to the corresponding comparators 9803 and 9804. At the same time, the two readout quantization threshold values are also input to a selector 9808. The comparators 9803 and 9804 compare the input coefficients and corresponding quantization threshold values to check if the quantization result becomes zero, and output the checking results.
The checking results output from the comparators 9803 and 9804 are input to a select signal generator 9806, the controller 9810, and an entropy encoder 9811. The select signal generator 9806 generates a select signal on the basis of the checking results output from the comparators 9803 and 9804. This select signal is generated to select one or both of the two coefficients to be quantized, which does or do not generate a zero quantization result, on the basis of the two checking results output from the comparators 9803 and 9804. If neither of the quantization results of these two coefficients become zero, the select signal is generated to time-divisionally select the two coefficients one by one. If both the quantization results of these two coefficients become zero, the select signal is generated to select one of these coefficients, since the result remains the same independently of the selected coefficient.
The controller 9810 generates a read control signal from the block memory 9802 on the basis of the checking results output from the comparators 9803 and 9804. If it is determined based on the two checking results output from the comparators 9803 and 9804 that at least one of the quantization results of the two coefficients to be quantized becomes zero, the control signal instructs to read out the next two coefficients; if it is determined that neither of the quantization results of the two coefficients become zero, the control signal instructs hold the values of these two coefficients for one cycle, and to read out the next two coefficients in the next cycle. The selector 9807 selects and outputs one of the two coefficients output from the block memory 9802 in accordance with the select signal output from the select signal generator 9806. Likewise, the selector 9808 selects and outputs one of the two quantization threshold values output from the quantization threshold value table 9805 in accordance with the select signal output from the select signal generator 9806. The coefficient output from the selector 9807 and the quantization threshold value output from the selector 9808 are input to a divider 9809.
The divider 9809 quantizes the input coefficient using the input quantization threshold value, and outputs a quantization result. This quantization result is input to the entropy encoder 9811. The entropy encoder 9811 obtains position information in a block on the basis of the quantization coefficient output from the divider 9809, and the checking results output from the comparators 9803 and 9804 to count a zero runlength, and executes entropy encoding, thus outputting encoded data.
The operation of the aforementioned encoding apparatus will be described below. A case will be exemplified below wherein the quantization results of two orthogonal transform coefficients output from the block memory 9802 become as follows. Note that values in ( ) indicate pairs of coefficients output from the block memory 9802, which are described in the order they are output from the block memory 9802. Also, “0” indicates that a quantization result is zero (insignificant coefficient), and “S” indicates that a quantization result is nonzero (significant coefficient).    Quantization Results: (S, 0), (S, S), (0, S), (S, 0)
When orthogonal transform coefficients for one block output from the orthogonal transformer 9801 are written in the block memory 9802, the controller 9810 outputs the read control signal, and every two coefficients begin to be read out from the block memory 9802.
FIG. 17 is a timing chart showing the operations in the aforementioned units. The controller 9810 outputs a read instruction in a period 9901. Note that the read control signal output from the controller 9810 indicates a read instruction if it is “1”, and an output hold instruction if it is “0”. In a period 9902, first two coefficients (S, 0) are read out from the block memory 9802 in accordance with the read instruction signal in the period 9901. These two coefficients are input to the comparators 9803 and 9804 together with corresponding two quantization threshold values read out from the quantization threshold value table 9805. The comparators 9803 and 9804 output checking results indicating that the quantization results of the two input coefficients respectively become significant and insignificant coefficients. Note that the checking result indicates an insignificant coefficient if it is “0”, and indicates a significant coefficient if it is “1”.
The checking results are input to the select signal generator 9806, controller 9810, and entropy encoder 9811 in the identical period 9902. Since the input checking results meet a condition that at least one coefficient is zero, the controller 9810 outputs the next read instruction, i.e., “1” to the block memory 9802. Also, the select signal generator 9806 outputs a select signal to the selectors 9807 and 9808 to select a significant one of the two coefficients in the period 9902. In this case, the select signal is “1” in case of (S, 0), or “0” in case of (0, S). In the period 9902, the selector 9807 selects and outputs a significant one of the two coefficients output from the block memory 9802, and the selector 9808 selects and outputs a quantization threshold value corresponding to the coefficient selected by the selector 9807. In the period 9902, the coefficient output from the selector 9807 is quantized by the divider 9809 using the quantization threshold value output from the selector 9808, thus outputting a quantization result. The quantization result is input to the entropy encoder 9811, and undergoes an entropy encoding process.
In a period 9903, the next two coefficients (S, S) are read out from the block memory 9802 in accordance with the read instruction signal output from the controller 9810 in the period 9902. These two coefficients are input to the comparators 9803 and 9804 together with corresponding two quantization threshold values read out from the quantization threshold value table 9805. The comparators 9803 and 9804 output checking results indicating that both the quantization results of the two input coefficients become significant coefficients. The checking results are input to the select signal generator 9806, controller 9810, and entropy encoder 9811 in the identical period 9903. Since the input checking results meet a condition that both the coefficients are nonzero, the controller 9810 outputs an output hold instruction, i.e., “0” to the block memory 9802.
In the period 9903, the select signal generator 9806 outputs a select signal to the selectors 9807 and 9808 to select an earlier one of the two coefficients in the zigzag scan order. In the period 9903, the selector 9807 selects and outputs an earlier one of the two coefficients in the zigzag scan order, which are output from the block memory 9802, and the selector 9808 selects and outputs a quantization threshold value corresponding to the coefficient selected by the selector 9807. In the period 9903, the coefficient output from the selector 9807 is quantized by the divider 9809 using the quantization threshold value output from the selector 9808, thus outputting a quantization result. The quantization result is input to the entropy encoder 9811, and undergoes an entropy encoding process.
In a period 9904, the block memory 9802 holds and outputs the two coefficients (S, S), which were output in the period 9903, in accordance with the output hold instruction signal output from the controller 9810 in the period 9903. These two coefficients are input to the comparators 9803 and 9804 together with corresponding two quantization threshold values read out from the quantization threshold value table 9805. The comparators 9803 and 9804 output checking results indicating that both the quantization results of the two input coefficients become significant coefficients. The checking results are input to the select signal generator 9806, controller 9810, and entropy encoder 9811 in the identical period 9903. Since the input checking results meet a condition that both the coefficients are nonzero, and that condition is met in two successive cycles, the controller 9810 outputs the next read instruction, i.e., “1” to the block memory 9802. On the other hand, in the identical period 9904, the select signal generator 9806 outputs a select signal to the selectors 9807 and 9808 to select a later one of the two coefficients in the zigzag scan order. In the period 9904, the selector 9807 selects and outputs a later one of the two coefficients in the zigzag scan order, which are output from the block memory 9802, and the selector 9808 selects and outputs a quantization threshold value corresponding to the coefficient selected by the selector 9807. In the period 9904, the coefficient output from the selector 9807 is quantized by the divider 9809 using the quantization threshold value output from the selector 9808, thus outputting a quantization result. The quantization result is input to the entropy encoder 9811, and undergoes an entropy encoding process.
In a period 9905, the next two coefficients (0, S) are read out from the block memory 9802 in accordance with the read instruction signal in the period 9904. These two coefficients are input to the comparators 9803 and 9804 together with corresponding two quantization threshold values read out from the quantization threshold value table 9805. The comparators 9803 and 9804 output checking results indicating that the quantization results of the two input coefficients respectively become insignificant and significant coefficients. The checking results are input to the select signal generator 9806, controller 9810, and entropy encoder 9811 in the identical period 9905. Since the input checking results meet a condition that at least one coefficient is zero, the controller 9810 outputs the next read instruction, i.e., “1” to the block memory 9802.
In the identical period 9905, the select signal generator 9806 outputs “0” to the selectors 9807 and 9808 since the two coefficients are (0, S). In the period 9905, the selector 9807 selects and outputs a significant one of the two coefficients output from the block memory 9802, and the selector 9808 selects and outputs a quantization threshold value corresponding to the coefficient selected by the selector 9807. In the period 9905, the coefficient output from the selector 9807 is quantized by the divider 9809 using the quantization threshold value output from the selector 9808, thus outputting a quantization result. The quantization result is input to the entropy encoder 9811, and undergoes an entropy encoding process.
In a period 9906, the next two coefficients (S, 0) are read out from the block memory 9802 in accordance with the read instruction signal in the period 9905. These two coefficients are input to the comparators 9803 and 9804 together with corresponding two quantization threshold values read out from the quantization threshold value table 9805. The comparators 9803 and 9804 output checking results indicating that the quantization results of the two input coefficients respectively become significant and insignificant coefficients. The checking results are input to the select signal generator 9806, controller 9810, and entropy encoder 9811 in the identical period 9906. Since the input checking results meet a condition that at least one coefficient is zero, the controller 9810 outputs the next read instruction, i.e., “1” to the block memory 9802.
In the identical period 9906, the select signal generator 9806 outputs “1” to the selectors 9807 and 9808 since the two coefficients are (S, 0). In the period 9906, the selector 9807 selects and outputs a significant one of the two coefficients output from the block memory 9802, and the selector 9808 selects and outputs a quantization threshold value corresponding to the coefficient selected by the selector 9807. In the period 9906, the coefficient output from the selector 9807 is quantized by the divider 9809 using the quantization threshold value output from the selector 9808, thus outputting a quantization result. The quantization result is input to the entropy encoder 9811, and undergoes an entropy encoding process. After that, the encoding process is repeated similarly.
In a decoding apparatus for decoding encoded data, as a technique for dequantizing quantized data, which is obtained by quantizing data having a given domain using a quantization threshold value having another domain, to data of the original domain, a conventional method of implementing such technique using a multiplier and clamp circuit is known. The multiplier and clamp circuit will be described below. In the following description, a case will be exemplified wherein quantized data, which is obtained by quantizing data having a domain from 0 to 1024 using a quantization threshold value having a domain from 1 to 255, is dequantized to data having the domain from 0 to 1024. FIG. 21 shows an example of the arrangement of a conventional dequantization device. The conventional dequantization device will be described below with reference to FIG. 21.
Reference numeral 91301 denotes a multiplier for multiplying input quantized data by a quantization threshold value to obtain a product, and outputting the product. The domain of the input quantized data is expressed by 11 bits since it ranges from 0 to 1024. Also, the domain of the quantization threshold value is expressed by 9 bits since it ranges from 0 to 255. Therefore, the size of the multiplier 91301 is 11 bits×8 bits. Reference numeral 91302 denotes a clamp circuit. When the output from the multiplier 91301 exceeds 1024 as the upper limit of the original domain, the clamp circuit 91302 outputs 1024; otherwise, the clamp circuit 91302 outputs the value output from the multiplier 91301. The output from the clamp circuit 91302 is the dequantized value to be obtained.
In the aforementioned arrangement of the conventional encoding apparatus shown in FIG. 5, since input of data in the last row of data that have undergone the first one-dimensional DCT to the transposition converter 502, and output of first data after transposition conversion from the transposition converter 502 cannot be made within an identical clock cycle unless a special RAM is used, the output timing must be delayed one clock cycle, and sufficiently high-speed processing cannot be achieved.
The present invention has been made in consideration of the aforementioned prior arts, and has as its first object to provide an image processing method and apparatus, which can execute high-speed 2D orthogonal transformation.
In the aforementioned conventional encoding apparatus shown in FIG. 16, since the input frequency of insignificant coefficients to the divider increases depending on the distribution of insignificant and significant coefficients in a unit block, the use efficiency of the divider lowers, and sufficiently high-speed processing cannot be achieved.
In the conventional decoding apparatus and, especially, the dequantization device, although the size of the multiplier is input 11 bits×8 bits, most of actual products fall within the range from 0 to 1024, and full 19 bits are rarely required as the output of the multiplier. Furthermore, in a system in which it is guaranteed that the dequantization result falls within the range from 0 to 1024, the output of the multiplier never exceeds 11 bits. Hence, due to the presence of many useless portions of the multiplier, the use efficiency of the multiplier suffers, and high-speed processing cannot be achieved.
The present invention has been made in consideration of the aforementioned prior arts, and has as its second object to execute a faster quantization process with a smaller circuit scale. Also, the present invention has as its third object to dequantize quantized data faster with a smaller circuit scale when the maximum value of dequantized data is set.